#ifndef _quicksort_h_
#define _quicksort_h_
#include <iostream>
#include <vector>
#include <cstdlib>
#include <time.h>
#include <string>

template <typename Comparable>
void quicksort(std::vector<Comparable> & a, int left, int right, int pivot = 1);

template <typename Compareble>
void sort(std::vector<Compareble> & a, int pivot = 1)
{
    quicksort(a, 0, a.size( ) - 1, pivot);
}

template <typename Comparable>
void insertionSort(std::vector<Comparable>& a, int left, int right)
{
    for(int p = left+1; p<=right; p++)
    {
        Comparable tmp = std::move(a[p]);
        int j;
        for(j=p; j>left && tmp<a[j-1]; --j)
            a[j] = std::move(a[j-1]);
        a[j] = std::move(tmp);
    }
}


template <typename Comparable>
const Comparable & median3(std::vector<Comparable> & a, int left, int right )
{
    int center = ( left + right ) / 2;
    if( a[center] < a[left] )
    std::swap( a[left], a[center] );
    if( a[right] < a[left] )
    std::swap( a[left], a[right] );
    if( a[right] < a[center] )
    std::swap( a[center], a[right] );

    // Place pivot at position right - 1
    std::swap( a[center], a[right - 1] );
    return a[right - 1];
}

template <typename Comparable>
const Comparable& randomChoice(std::vector<Comparable>& a, int left, int right)
{
    srand(time(0));
    int ind = rand()%(right-left+1) + left;
    // Place pivot at position right-1
    std::swap(a[ind], a[right-1]);
    return a[right-1];
}


/**
* Internal quicksort method that makes recursive calls.
* Uses median-of-three partitioning and a cutoff of 10.
* a is an array of Comparable items.
* left is the left-most index of the subarray.
* right is the right-most index of the subarray.
*/
template <typename Comparable>
void quicksort(std::vector<Comparable> & a, int left, int right, int pivot)
{
    if(left + 10 <= right)
    {
        if(pivot == 1)
            const Comparable & pivot = median3(a, left, right);
        else
            const Comparable & pivot = randomChoice(a, left, right);
        // Begin partitioning
        int i = left, j = right - 1;
        for( ; ; )
        {
            while(a[++i] < pivot) { }
            while(pivot < a[--j]) { }
            if(i < j)
                std::swap(a[i], a[j]);
            else
                break;
        }
        std::swap(a[i] , a[right - 1]); // Restore pivot
        quicksort(a, left, i - 1, pivot); // Sort small elements
        quicksort(a, i + 1, right, pivot); // Sort large elements
    }
    else // Do an insertion sort on the subarray
        insertionSort(a, left, right);
}


#endif // !_quicksort_h_
